﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Solution
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }


        /// <summary>
        /// leetcode  938  二叉搜索树的范围和
        /// </summary>
        /// <param name="root"></param>
        /// <param name="low"></param>
        /// <param name="high"></param>
        /// <returns></returns>
        public int RangeSumBST(TreeNode root, int low, int high)
        {
            if (root == null)
                return 0;
            if (root.val < low)
                return RangeSumBST(root.right, low, high);
            if (root.val > high)
                return RangeSumBST(root.left, low, high);
            return root.val + RangeSumBST(root.right, low, high) + RangeSumBST(root.left, low, high);
        }


        /// <summary>
        /// leetcode  142  环形链表2（快慢指针）
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode DetectCycle(ListNode head)
        {
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null)
            {
                slow = slow.next;
                if (fast.next == null)
                    return null;
                fast = fast.next.next;
                if (slow == fast)
                {
                    fast = head;
                    while (fast != slow)
                    {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }

        /// <summary>
        /// leetcode  02.07  链表相交
        /// </summary>
        /// <param name="headA"></param>
        /// <param name="headB"></param>
        /// <returns></returns>
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            if (headA == null || headB == null)
            {
                return null;
            }
            ListNode nodeA = headA, nodeB = headB;
            while (nodeA != nodeB)
            {
                nodeA = nodeA == null ? nodeB : nodeA.next;
                nodeB = nodeB == null ? nodeA : nodeB.next;
            }
            return nodeA;
        }

        /// <summary>
        /// leetcode  19  删除链表的倒数第N个结点
        /// </summary>
        /// <param name="head"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            ListNode tmp = new ListNode(n, head);
            ListNode current = tmp;
            ListNode pre = tmp;
            int count = 0;
            while (current != null && count < n)
            {
                current = current.next;
                count++;
            }
            while (current.next != null)
            {
                pre = pre.next;
                current = current.next;
            }
            current = pre.next;
            pre.next = current.next;

            return tmp.next;
        }

        /// <summary>
        /// leetcode  206  反转链表
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode ReverseList(ListNode head)
        {
            ListNode pre, cur;
            pre = null;
            cur = head;
            while (cur != null)
            {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return head;
        }
    }
}
